package aSortModel;

import java.util.Arrays;

/**
 * 归并排序算法是一个递归过程，
 * 边界条件为当输入序列仅有一个元素时，直接返回，具体过程如下：
 * 如果输入内只有一个元素，则直接返回，
 * 否则将长度为 n 的输入序列分成两个长度为 n/2 的子序列；
 * 分别对这两个子序列进行归并排序，使子序列变为有序状态；
 * 设定两个指针，分别指向两个已经排序子序列的起始位置；
 * 比较两个指针所指向的元素，选择相对小的元素放入到合并空间（用于存放排序结果），
 * 并移动指针到下一位置；重复步骤 3 ~4 直到某一指针达到序列尾；
 * 将另一序列剩下的所有元素直接复制到合并序列尾。
 */
public class Merge_sort {
    public static int[] mergeSort(int[] arr) {
        if (arr.length <= 1) {
            return arr;
        }
        int middle = arr.length / 2;
        int[] arr_1 = Arrays.copyOfRange(arr, 0, middle);
        int[] arr_2 = Arrays.copyOfRange(arr, middle, arr.length);
        return merge(mergeSort(arr_1), mergeSort(arr_2));
    }
    public static int[] merge(int[] arr_1, int[] arr_2) {
        int[] sorted_arr = new int[arr_1.length + arr_2.length];
        int idx = 0, idx_1 = 0, idx_2 = 0;
        while (idx_1 < arr_1.length && idx_2 < arr_2.length) {
            if (arr_1[idx_1] < arr_2[idx_2]) {
                sorted_arr[idx] = arr_1[idx_1];
                idx_1 += 1;
            } else {
                sorted_arr[idx] = arr_2[idx_2];
                idx_2 += 1;
            }
            idx += 1;
        }
        if (idx_1 < arr_1.length) {
            while (idx_1 < arr_1.length) {
                sorted_arr[idx] = arr_1[idx_1];
                idx_1 += 1;
                idx += 1;
            }
        } else {
            while (idx_2 < arr_2.length) {
                sorted_arr[idx] = arr_2[idx_2];
                idx_2 += 1;
                idx += 1;
            }
        }
        return sorted_arr;
    }
}
